package week_eight;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class NetworkDelayTime_743 {
    public int networkDelayTime(int[][] times, int n, int k) {
        //Dijkstra算法
        int[] dist = new int[n + 1];
        boolean[] visited = new boolean[n + 1];

        //建图
        List<List<Integer>> ver = new ArrayList<>();
        List<List<Integer>> edge = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            ver.add(new ArrayList<>());
            edge.add(new ArrayList<>());
            dist[i] = (int) 1e9;
        }
        dist[k] = 0;//起点为0
        for (int[] uvw : times) {
            int x = uvw[0];
            int y = uvw[1];
            int z = uvw[2];
            ver.get(x).add(y);
            edge.get(x).add(z);
        }

        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        q.offer(new int[]{dist[k], k});
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            // int distx = curr[0];
            int x = curr[1];
            if (visited[x]) continue;
            visited[x] = true;
            for (int i = 0; i < ver.get(x).size(); i++) {
                int y = ver.get(x).get(i);
                int z = edge.get(x).get(i);
                if (dist[y] > dist[x] + z) {
                    dist[y] = dist[x] + z;
                    q.offer(new int[]{dist[y], y});
                    // System.out.println("Update "+y+" dist to: " +dist[y]);
                }
            }
        }

        //bellman-ford
        // for(int round=1;round<n;round++){
        //     boolean flag = false;

        //     for(int[] edge : times){
        //         int x = edge[0];
        //         int y = edge[1];
        //         int z = edge[2];
        //         if(dist[x]+z<dist[y]){
        //             dist[y] = dist[x]+z;
        //             flag = true;
        //         }

        //     }
        //     if(!flag) break;
        // }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }

        if (ans == (int) 1e9) return -1;
        return ans;
    }
}
